Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
In [16]:
import pdb
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
# nums list length
nums_len = len(nums)
# sort nums
nums.sort()
# pdb.set_trace()
delta = abs(target - nums[0] - nums[1] - nums[2])
ans = 0
for i in range(nums_len - 2):
# 次级目标
t_target = target - nums[i]
j = i + 1
k = nums_len - 1
while j < k:
tmp = t_target - nums[j]- nums[k]
if tmp == 0:
return nums[i] + nums[j] + nums[k]
if abs(tmp) <= delta:
delta = abs(tmp)
ans = nums[i] + nums[j] + nums[k]
# print(i, j, k, ans1, ans2, ans3)
if tmp > 0 :
j += 1
else:
k -= 1
return ans
In [17]:
Solution().threeSumClosest([-1,2, 1, -4], 1) # answer is 2
Out[17]:
In [18]:
Solution().threeSumClosest([0, 1, 2], 3)# answer 3 此处没通过是因为27行tmp<= delta,我写成delta<temp
Out[18]:
In [19]:
Solution().threeSumClosest([1,1,1,0], -100) # answer is 2 此处没有通过是因为忽略tmp和delta应该都是绝对值比较，不能只比较大小，abs(tmp)<= delta
Out[19]:
In [20]:
Solution().threeSumClosest([1,2,4,8,16,32,64,128], 82) # answer is 82 此处没有通过是因为tmp要知道left和right的走向 修改tmp>0 left += 1, or right -= 1
Out[20]:
In [22]:
Solution().threeSumClosest([1,1,-1,-1,3], -1) # answer is -1 ,搞不懂一模一样的代码，当前代码可以通过，自己重新打的一遍死活不过，对比了一下，没有发现哪里有所不同
Out[22]:
In [ ]: